//
//  prime_constexpr.hpp
//  prime
//
//  Created by 杨永康 on 2021/2/25.
//

#ifndef prime_constexpr_h
#define prime_constexpr_h
template<typename T=ULL>
constexpr T  mod[5]={4,3,3,3,3};
template<typename T=ULL>
constexpr T  delta[5][4]={{2,4,2,2},{2,6,2},{2,4,4},{4,2,4},{6,2,2}};
template<typename T=ULL>
constexpr T table[5][10][2]={{
    {1,0},
    {0,0},
    {1,1},
    {0,1},
    {3,2},
    {2,2},
    {1,2},
    {0,2},
    {1,3},
    {0,3},
},{
    {1,0},
    {0,0},
    {1,1},
    {0,1},
    {5,2},
    {4,2},
    {3,2},
    {2,2},
    {1,2},
    {0,2}
},{
    {1,0},
    {0,0},
    {1,1},
    {0,1},
    {3,2},
    {2,2},
    {1,2},
    {0,2},
    {3,0},
    {2,0}
},{
    {3,0},
    {2,0},
    {1,0},
    {0,0},
    {3,1},
    {2,1},
    {1,1},
    {0,1},
    {1,2},
    {0,2}
},{
    {1,0},
    {0,0},
    {5,1},
    {4,1},
    {3,1},
    {2,1},
    {1,1},
    {0,1},
    {1,2},
    {0,2}
}};
template<typename T=ULL>
constexpr T result[1083]={0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 2, 1, 2, 0, 2, 1, 2, 1, 3, \
    0, 3, 1, 3, 0, 2, 0, 3, 1, 2, 1, 4, 0, 4, 0, 2, 1, 3, 0, 4, 1, 3, 1, \
    4, 0, 5, 1, 4, 0, 3, 0, 5, 1, 3, 0, 4, 0, 6, 1, 3, 1, 5, 0, 6, 0, 2, \
    1, 5, 0, 6, 1, 5, 1, 5, 0, 7, 0, 4, 1, 5, 0, 8, 1, 5, 0, 4, 0, 9, 1, \
    4, 0, 5, 0, 7, 0, 3, 1, 6, 0, 8, 1, 5, 1, 6, 0, 8, 1, 6, 1, 7, 0, 10, \
    1, 6, 0, 6, 0, 12, 0, 4, 0, 5, 0, 10, 0, 3, 1, 7, 0, 9, 1, 6, 0, 5, \
    0, 8, 1, 7, 1, 8, 0, 11, 0, 6, 0, 5, 0, 12, 1, 4, 1, 8, 0, 11, 0, 5, \
    1, 8, 0, 10, 0, 5, 1, 6, 0, 13, 1, 9, 0, 6, 0, 11, 1, 7, 0, 7, 0, 14, \
    1, 6, 1, 8, 0, 13, 0, 5, 0, 8, 0, 11, 1, 7, 1, 9, 0, 13, 1, 8, 1, 9, \
    0, 14, 0, 7, 0, 7, 0, 19, 0, 6, 1, 8, 0, 13, 0, 7, 0, 9, 0, 11, 0, 7, \
    1, 7, 0, 12, 1, 9, 1, 7, 0, 15, 1, 9, 0, 9, 0, 18, 1, 8, 1, 9, 0, 16, \
    0, 6, 0, 9, 0, 16, 1, 9, 0, 8, 0, 14, 1, 10, 0, 9, 0, 16, 1, 8, 0, 9, \
    0, 19, 1, 7, 1, 11, 0, 16, 0, 7, 1, 14, 0, 16, 1, 8, 1, 12, 0, 17, 0, \
    10, 0, 8, 0, 19, 1, 8, 0, 11, 0, 21, 0, 9, 0, 10, 0, 15, 0, 8, 1, 12, \
    0, 17, 1, 9, 1, 10, 0, 15, 1, 11, 0, 11, 0, 20, 0, 7, 0, 10, 0, 24, \
    0, 6, 1, 11, 0, 19, 0, 9, 1, 13, 0, 17, 0, 10, 0, 9, 0, 16, 1, 13, 1, \
    10, 0, 20, 1, 9, 0, 10, 0, 22, 1, 8, 0, 14, 0, 18, 0, 8, 1, 14, 0, \
    18, 0, 10, 1, 11, 0, 22, 0, 13, 1, 10, 0, 19, 1, 12, 0, 9, 0, 27, 1, \
    11, 0, 11, 0, 21, 0, 7, 1, 14, 0, 17, 1, 11, 0, 13, 0, 20, 0, 13, 1, \
    11, 0, 21, 0, 10, 0, 11, 0, 30, 1, 11, 1, 12, 0, 21, 0, 9, 0, 14, 0, \
    19, 1, 13, 1, 11, 0, 21, 0, 14, 1, 13, 0, 21, 1, 12, 0, 13, 0, 27, 1, \
    12, 0, 12, 0, 24, 0, 9, 1, 16, 0, 28, 1, 12, 1, 13, 0, 24, 1, 15, 0, \
    13, 0, 23, 0, 14, 0, 11, 0, 29, 1, 11, 0, 14, 0, 23, 0, 9, 1, 19, 0, \
    22, 1, 13, 0, 13, 0, 23, 0, 13, 1, 15, 0, 27, 1, 15, 0, 14, 0, 32, 1, \
    11, 0, 14, 0, 23, 0, 11, 0, 17, 0, 24, 1, 11, 1, 15, 0, 25, 0, 14, 0, \
    17, 0, 22, 0, 13, 0, 14, 0, 30, 0, 10, 1, 13, 0, 30, 0, 11, 1, 19, 0, \
    23, 0, 11, 0, 11, 0, 23, 1, 18, 0, 14, 0, 24, 1, 13, 0, 13, 0, 31, 1, \
    11, 1, 16, 0, 26, 0, 12, 1, 19, 0, 25, 0, 12, 0, 13, 0, 29, 1, 16, 0, \
    15, 0, 27, 1, 12, 0, 15, 0, 32, 1, 12, 1, 14, 0, 27, 0, 13, 1, 20, 0, \
    26, 0, 15, 1, 19, 0, 26, 1, 18, 1, 17, 0, 31, 0, 12, 0, 16, 0, 41, 0, \
    10, 1, 14, 0, 28, 0, 15, 0, 18, 0, 25, 1, 17, 1, 16, 0, 27, 1, 21, 0, \
    15, 0, 29, 1, 13, 0, 19, 0, 41, 1, 14, 1, 16, 0, 31, 0, 11, 0, 21, 0, \
    33, 0, 15, 1, 17, 0, 28, 1, 21, 0, 16, 0, 30, 1, 16, 0, 16, 0, 39, 0, \
    11, 1, 19, 0, 30, 0, 14, 0, 24, 0, 31, 1, 18, 0, 19, 0, 24, 0, 16, 1, \
    17, 0, 37, 0, 14, 0, 15, 0, 39, 1, 14, 0, 15, 0, 31, 0, 15, 1, 21, 0, \
    31, 0, 15, 1, 19, 0, 29, 0, 18, 1, 19, 0, 31, 1, 18, 0, 19, 0, 39, 0, \
    14, 1, 17, 0, 35, 0, 15, 1, 21, 0, 30, 1, 17, 0, 17, 0, 31, 0, 26, 1, \
    18, 0, 32, 1, 16, 0, 15, 0, 44, 0, 14, 0, 18, 0, 30, 0, 15, 1, 22, 0, \
    34, 0, 17, 0, 14, 0, 38, 1, 21, 0, 16, 0, 32, 0, 16, 0, 14, 0, 39, 1, \
    18, 1, 20, 0, 34, 0, 17, 0, 20, 0, 29, 1, 16, 1, 21, 0, 34, 1, 22, 1, \
    22, 0, 33, 0, 18, 0, 17, 0, 51, 1, 18, 0, 17, 0, 32, 0, 15, 0, 25, 0, \
    31, 0, 20, 1, 19, 0, 39, 1, 18, 1, 17, 0, 33, 1, 17, 0, 21, 0, 46, 0, \
    18, 0, 19, 0, 36, 0, 14, 1, 25, 0, 39, 1, 21, 1, 18, 0, 37, 1, 23, 0, \
    19, 0, 34, 0, 20, 0, 19, 0, 48, 0, 15, 0, 17, 0, 34, 0, 15, 1, 31, 0, \
    31, 1, 20, 0, 18, 0, 35, 0, 23, 1, 20, 0, 47, 0, 18, 0, 18, 0, 43, 1, \
    17, 0, 20, 0, 36, 0, 18, 1, 24, 0, 34, 1, 18, 0, 20, 0, 33, 1, 25, 0, \
    23, 0, 37, 1, 19, 0, 22, 0, 45, 0, 16, 0, 18, 0, 45, 0, 17, 1, 27, 0, \
    32, 1, 17, 0, 19, 0, 35, 1, 26, 0, 17, 0, 39, 1, 20, 0, 23, 0, 52, 0, \
    13, 1, 25, 0, 37, 0, 17, 1, 28, 0, 36, 0, 18, 0, 18, 0, 42, 0, 25, 1, \
    23, 0, 39, 1, 18, 0, 20, 0, 51, 1, 18, 1, 22, 0, 42, 0, 18, 0, 25, 0, \
    36, 1, 21, 1, 27, 0, 40, 0, 26, 1, 22, 0, 39, 0, 19, 0, 19, 0, 57, 1, \
    18, 1, 24, 0, 44, 0, 19, 0, 27, 0, 37, 1, 24, 1, 24, 0, 39, 0, 25, 1, \
    21, 0, 40, 0, 20, 0, 27, 0, 54, 0, 20};
template<typename T>
constexpr T prime_list[100]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, \
    67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, \
    139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, \
    223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, \
    293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, \
    383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, \
    463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541};
constexpr bool prime_bool[1001]={0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, \
    1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, \
    0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, \
    0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, \
    0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, \
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, \
    0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, \
    0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, \
    0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, \
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, \
    0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, \
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, \
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, \
    0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, \
    0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, \
    0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, \
    0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, \
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, \
    0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, \
    0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, \
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, \
    0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, \
    0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, \
    0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, \
    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, \
    0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, \
    0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, \
    0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0};

#endif /* prime_constexpr_h */
